package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 构建乘积数组
 *
 * @author yuhushuan
 * @date 2020/7/4 11:50
 */
public class _66_1_ConstructArray {

    /**
     * 时间复杂度 O(n*n) 和 直接乘积没区别
     *
     * @param A
     * @return
     */
    private static int[] constructArray_Solution1(int A[]) {
        if (A == null) {
            return null;
        }
        int n = A.length;
        int[] B = new int[n];

        // 当 n = 1 时
        B[0] = 1;
        // i 为 n 的具体数目
        for (int i = 1; i < n; ++i) {
            B[i] = B[i - 1] * A[i - 1];
            for (int j = 0; j < i; ++j) {
                B[j] = B[j] * A[i];
            }
        }
        return B;
    }

    private static int[] constructArray(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }
        if (A.length == 1) {
            return new int[]{1};
        }
        int length = A.length;
        // 辅助数组 C[i] = C[i-1] * A[i-1]
        int[] C = new int[length];
        C[0] = 1;
        for (int i = 1; i < length; ++i) {
            C[i] = C[i - 1] * A[i - 1];
        }
        // 辅助数组 D
        int[] D = new int[length];
        D[length - 1] = 1;
        for (int i = length - 2; i >= 0; --i) {
            D[i] = D[i + 1] * A[i + 1];
        }
        int[] B = new int[length];
        for (int i = 0; i < length; ++i) {
            B[i] = C[i] * D[i];
        }
        return B;
    }

    public static void main(String[] args) {
        // 功能测试
        // 数组包含正数、负数、一个0、多个0
        print(new int[]{2, 3, 4});
        print(new int[]{2, 3, -4});

        print(new int[]{2, 3, 4, 0});
        print(new int[]{2, 3, 0, 4, 0});

        // 边界值测试
        print(new int[]{});
        print(new int[]{2});
    }

    private static void print(int[] numbers) {
        System.out.println("数组：" + Arrays.toString(numbers));
//        System.out.println("乘积一：" + Arrays.toString(constructArray_Solution1(numbers)));
        System.out.println("乘积：" + Arrays.toString(constructArray(numbers)));
        System.out.println();
    }

}
